package com.example.demo.leetcode.top100;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _75前K个高频元素
 * @description
 * @date 2023/06/26 10:03
 * <p>
 * ******************************************************
 */
public class _75前K个高频元素 {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, FrequentTimes> numToTimes = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            FrequentTimes item = numToTimes.getOrDefault(nums[i], new FrequentTimes(0, nums[i]));
            item.setTimes(item.getTimes() + 1);
            numToTimes.put(nums[i], item);
        }


        PriorityQueue<FrequentTimes> pq = new PriorityQueue<>((a, b) -> a.getTimes() - b.getTimes());
        for (FrequentTimes value : numToTimes.values()) {
            pq.offer(value);
            if (pq.size() > k) {
                pq.poll();
            }
        }

        int[] result = new int[k];
        int i = 0;
        while (!pq.isEmpty()) {
            result[i++] = pq.poll().getNum();
        }

        return result;
    }

    class FrequentTimes {
        private int times;
        private int num;

        public FrequentTimes(int times, int num) {
            this.times = times;
            this.num = num;
        }

        public int getTimes() {
            return times;
        }

        public void setTimes(int times) {
            this.times = times;
        }

        public int getNum() {
            return num;
        }

        public void setNum(int num) {
            this.num = num;
        }
    }


    public static void main(String[] args) {
        _75前K个高频元素 s = new _75前K个高频元素();
        System.out.println(Arrays.toString(s.topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2)));
    }
}

